#ifndef HASH_BASIC_H_
#define HASH_BASIC_H_

/*******************************************************************************
 ** Name: hash_basic.h                                                        **
 ** Description:                   **
 **                                                                           **
 ** Open Source Initiative (OSI) Approved License: CDDL                       **
 **                                                                           **
 ** The contents of this file are subject to the terms of the                 **
 ** Common Development and Distribution License, Version 1.0 only             **
 ** (the "License").  You may not use this file except in compliance          **
 ** with the License.                                                         **
 **                                                                           **
 ** You can find a copy of the license in the license.txt within              **
 ** this distribution or at http://opensource.org/licenses/CDDL-1.0.          **
 ** Software distributed under the License is distributed on an "AS IS"       **
 ** basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.           **
 ** See the License for the specific language governing permissions           **
 ** and limitations under the License.                                        **
 **                                                                           **
 ** When distributing Covered Code, include this CDDL header in each          **
 ** file and include the License file at $HOME/license.txt.                   **
 ** If applicable, add the following below this header, with the indicated    **
 ** fields enclosed by brackets "[]" replaced with your own identifying       **
 ** information: Portions Copyright [yyyy] [name of copyright owner]          **
 **                                                                           **
 ** Copyright (c) 2009-2010  Barry Gian James <gian@avr-firmware.net>         **
 ** All rights reserved.                                                      **
 **                                                                           **
 ** Ref: $HeadURL$
 ******************************************************************************/
// Portions (C) 2011-13 Open Design Strategies, LLC.
// All Rights Reserved

// $Id$
// Last Modified $Date$ by $Author$
#include "common.h"

BEGIN_NAMESPACE(std)
BEGIN_NAMESPACE(hash)

// The basic hashtable consists of buckets of linked hash_entries

//! @class _hash_entry
//! @brief The chained list within a hash bucket
template <class K, class D>
struct _hash_entry
{
	_hash_entry() { prev = next = NULL; key = K(); }
	_hash_entry(const K & k, const D &d) : key(k), data(d) { prev = next = NULL; }
	_hash_entry(const _hash_entry<K,D> & he) : key(he.key), data(he.data) { prev = next = NULL; }

	_hash_entry<K,D> & operator = (const _hash_entry<K,D> &);
	int operator == (const _hash_entry<K,D> & he) { return ((he.data == data) && (he.key == key)); }
	int operator != (const _hash_entry<K,D> & he) { return ((he.data != data) && (he.key == key)); }

	_hash_entry<K,D> * prev, * next;
	K	key;
	D	data;
};

template <class K, class D>
class hash_bucket
{
public:
	hash_bucket() { _first = NULL; }
	~hash_bucket() { _clear(); }

protected:
	_hash_entry<K,D> *	_first;
	void _clear() {
		if (_first != NULL) {
			_hash_entry<K,D> * next, * curr = _first;

			while (curr != NULL) {
				next = curr->next;
				delete curr;
				curr = next;
			}
			_first = NULL;
		}
	}
};


long genkey(const char * s, uint8_t len)
{
	register long x = 0;
	register uint8_t n = 0;
	register uint8_t c;

	while(n++ < len)
	{
		c = *s;
		if ((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z'))
			x = ((x*0x63c63cd9L)+0x9c39c33dL + c);
		else if (c >= '0' && c <= '9')
			x = ((x*0x63c63cd9L)+0x9c39c33dL + (c - '0'+'z'+1));
		else break;
		++s;
	}
	return x;
}

int hash_basic(uint16_t nbuckets, void * data)
{
	unsigned long n = 0;
	for (char * ptr = data; *ptr; ++ptr)
	{
		n <<= 1;
		n += *ptr;
	}
	return (int)(n % nbuckets);
}

END_NAMESPACE()
END_NAMESPACE()

#endif /* HASH_BASIC_H_ */
